Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
Loading...
Searching...
No Matches
list.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2015 Roc authors
3 *
4 * This Source Code Form is subject to the terms of the Mozilla Public
5 * License, v. 2.0. If a copy of the MPL was not distributed with this
6 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 */
8
9//! @file roc_core/list.h
10//! @brief Intrusive doubly-linked list.
11
12#ifndef ROC_CORE_LIST_H_
13#define ROC_CORE_LIST_H_
14
15#include "roc_core/list_node.h"
17#include "roc_core/ownership.h"
18#include "roc_core/panic.h"
19#include "roc_core/stddefs.h"
20
21namespace roc {
22namespace core {
23
24//! Intrusive doubly-linked list.
25//!
26//! @tparam T defines object type, it should inherit ListNode.
27//! @tparam Ownership defines ownership policy which is used to acquire an element
28//! ownership
29//! when it's added to the list and release ownership when it's removed from the list
30template <class T, template <class TT> class Ownership = RefCntOwnership>
31class List : public NonCopyable<> {
32public:
33 //! Pointer type.
34 //! @remarks
35 //! either raw or smart pointer depending on the ownership policy.
36 typedef typename Ownership<T>::Pointer Pointer;
37
38 //! Initialize empty list.
40 : size_(0) {
41 head_.prev = &head_;
42 head_.next = &head_;
43 head_.list = this;
44 }
45
46 //! Release ownership of containing objects.
48 ListNode::ListNodeData* next_data;
49
50 for (ListNode::ListNodeData* data = head_.next; data != &head_;
51 data = next_data) {
52 roc_panic_if(data == NULL);
53 check_is_member_(data, this);
54
55 next_data = data->next;
56 data->list = NULL;
57
58 Ownership<T>::release(*container_of_(data));
59 }
60
61 head_.list = NULL;
62 }
63
64 //! Get number of elements in list.
65 size_t size() const {
66 return size_;
67 }
68
69 //! Get first list element.
70 //! @returns
71 //! first element or NULL if list is empty.
72 Pointer front() const {
73 if (size_ == 0) {
74 return NULL;
75 }
76 return container_of_(head_.next);
77 }
78
79 //! Get last list element.
80 //! @returns
81 //! last element or NULL if list is empty.
82 Pointer back() const {
83 if (size_ == 0) {
84 return NULL;
85 }
86 return container_of_(head_.prev);
87 }
88
89 //! Get list element next to given one.
90 //!
91 //! @returns
92 //! list element following @p element if @p element is not
93 //! last, or NULL otherwise.
94 //!
95 //! @pre
96 //! @p element should be member of this list.
97 Pointer nextof(T& element) const {
98 ListNode::ListNodeData* data = element.list_node_data();
99 check_is_member_(data, this);
100
101 if (data->next == &head_) {
102 return NULL;
103 }
104 return container_of_(data->next);
105 }
106
107 //! Prepend element to list.
108 //!
109 //! @remarks
110 //! - prepends @p element to list
111 //! - acquires ownership of @p element
112 //!
113 //! @pre
114 //! @p element should not be member of any list.
115 void push_front(T& element) {
116 if (size_ == 0) {
117 insert_(element, NULL);
118 } else {
119 insert_(element, container_of_(head_.next));
120 }
121 }
122
123 //! Append element to list.
124 //!
125 //! @remarks
126 //! - appends @p element to list
127 //! - acquires ownership of @p element
128 //!
129 //! @pre
130 //! @p element should not be member of any list.
131 void push_back(T& element) {
132 insert_(element, NULL);
133 }
134
135 //! Insert element into list.
136 //!
137 //! @remarks
138 //! - inserts @p element before @p before
139 //! - acquires ownership of @p element
140 //!
141 //! @pre
142 //! @p element should not be member of any list.
143 //! @p before should be member of this list or NULL.
144 void insert_before(T& element, T& before) {
145 insert_(element, &before);
146 }
147
148 //! Remove element from list.
149 //!
150 //! @remarks
151 //! - removes @p element from list
152 //! - releases ownership of @p element
153 //!
154 //! @pre
155 //! @p element should be member of this list.
156 void remove(T& element) {
157 ListNode::ListNodeData* data = element.list_node_data();
158 check_is_member_(data, this);
159
160 data->prev->next = data->next;
161 data->next->prev = data->prev;
162
163 data->list = NULL;
164
165 size_--;
166
167 Ownership<T>::release(element);
168 }
169
170private:
171 static inline T* container_of_(ListNode::ListNodeData* data) {
172 return static_cast<T*>(data->container_of());
173 }
174
175 static void check_is_member_(const ListNode::ListNodeData* data, const List* list) {
176 if (data->list != list) {
177 roc_panic("list element is member of wrong list: expected %p, got %p",
178 (const void*)list, (const void*)data->list);
179 }
180 }
181
182 void insert_(T& element, T* before) {
183 ListNode::ListNodeData* data_new = element.list_node_data();
184 check_is_member_(data_new, NULL);
185
186 ListNode::ListNodeData* data_before;
187 if (before != NULL) {
188 data_before = before->list_node_data();
189 check_is_member_(data_before, this);
190 } else {
191 data_before = &head_;
192 }
193
194 data_new->next = data_before;
195 data_new->prev = data_before->prev;
196
197 data_before->prev->next = data_new;
198 data_before->prev = data_new;
199
200 data_new->list = this;
201
202 size_++;
203
204 Ownership<T>::acquire(element);
205 }
206
207 ListNode::ListNodeData head_;
208 size_t size_;
209};
210
211} // namespace core
212} // namespace roc
213
214#endif // ROC_CORE_LIST_H_
Intrusive doubly-linked list.
Definition: list.h:31
void push_back(T &element)
Append element to list.
Definition: list.h:131
Pointer nextof(T &element) const
Get list element next to given one.
Definition: list.h:97
void remove(T &element)
Remove element from list.
Definition: list.h:156
void insert_before(T &element, T &before)
Insert element into list.
Definition: list.h:144
Pointer front() const
Get first list element.
Definition: list.h:72
Ownership< T >::Pointer Pointer
Pointer type.
Definition: list.h:36
~List()
Release ownership of containing objects.
Definition: list.h:47
Pointer back() const
Get last list element.
Definition: list.h:82
size_t size() const
Get number of elements in list.
Definition: list.h:65
List()
Initialize empty list.
Definition: list.h:39
void push_front(T &element)
Prepend element to list.
Definition: list.h:115
Base class for non-copyable objects.
Definition: noncopyable.h:23
Linked list node.
Root namespace.
Non-copyable object.
Ownership policies.
Panic function.
#define roc_panic_if(x)
Panic if condition is true.
Definition: panic.h:26
#define roc_panic(...)
Print error message and terminate program gracefully.
Definition: panic.h:42
Commonly used types and functions.
ListNode * container_of()
Get ListNode object that contains this ListData object.
Definition: list_node.h:48
ListNodeData * next
Next list element.
Definition: list_node.h:34
ListNodeData * prev
Previous list element.
Definition: list_node.h:31
void * list
The list this node is member of.
Definition: list_node.h:39